﻿/*二叉树:
 * 一、定义：
 * 二叉树的每个结点至多只有两棵字数（不存在度大于2的结点），二叉树的字数有左右之分，
 * 次序不能颠倒。
 * 二叉树的第i层至多有2^(i-1)个结点；
 * 深度为k的二叉树至多有2^k-1个结点；
 * 对任何一棵二叉树T,如果其终端结点数为N0，度为2的结点数为N2,则N0=N2+1
 *
 * 二、关键词：
 * 深度：树的深度，从根节点数到它的叶节点。
 * 高度：树的高度，从叶子结点数到它的根节点。
 * 二叉树的深度是从根节点开始（深度为1）自顶向下逐层累加的，
 * 二叉树的高度是从叶节点开始（高度为1）自底向上逐层累加的。
 * 虽然树的高度和深度一样，但是具体到树的某个结点，其深度和高度是不一样的。
 * 三、分类：
 * 1 完全二叉树，若设二叉树的高度为h,除第h层外，其他各层（1~h-1）的结点数都
 * 达到最大个数，第h层都有叶子结点，并且叶子结点都是从左到右依次排序。
 * (所有叶子结点都在最后下面一层，而且叶子结点都是从左到右依次排序。)
 * （每层结点都完全填满，在最后一层上如果不是满的，则只缺少右边的若干结点。）
 * 2 满二叉树，除了叶子结点外每个结点都有左右子结点且叶子结点都处在最底层的二叉树。
 * 3 完美二叉树：所有的非叶子结点都有两个孩子，所有的叶子结点都在同一层，即每层结点都填满。
 * 4 二叉排序树或者是一棵空树，或者具有以下性质：
 * 1）若左子树不空，则左子树上的值都小于它的根节点的值；
 * 2）若右子树不空，则右子树上的值都小于它的根节点的值；
 * 3）左右子树也分别为儿茶排序树。
 * 5 平衡二叉树，平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，
 * 且具有以下性质：它是一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右
 * 两个子树都是一颗平衡二叉树。
 *
 * 四、二叉树的性质：
 * 1)在非空二叉树中，第i层的结点数不超过2^(i-1)  i>=1;
 * 2)深度为h的二叉树最多有2^h-1个结点（h>=1),最少有h个结点。
 * 3)对于任意一个二叉树，如果其叶节点树为N0,而度数为2的结点总数为N2,则N0=N2+1
 * 4)具有n个结点的完全二叉树深度为log2(n+1)
 * 5)有n个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
 * 若i为结点编号，则如果i>1，则其父节点的编号为i/2
 * 如果2*i<=n,则其左儿子（即左子树的根节点）的编号为2*i;若2*i>n,则无左儿子；
 * 如果2*i+1<=n,则其右儿子的结点编号为2*i+1;若2*i+1>n,则无右儿子。
 * 6)给定n个结点，能构成h(n)种不同的二叉树。
 * h(n)为卡特兰数的第n项。h(n)=C(2*n,n)/(n+1).
 * 7)设有i个结点，L为所有结点的道路长度总和，J为叶的道路长度总和j=L+2i
 * 五、二叉树不是树的特例
 * 1 二叉树与无序树不同
 * 二叉树的每个结点，最多有2棵子树，并且有左右之分。
 * 二叉树并非是树的特殊形式，他们是两种不同的数据结构。
 * 2二叉树与度为2的有序树不同
 * 在度为2的有序树中，虽然一个结点的孩子之间是有左右次序的。但是当该结点只有
 * 一个孩子时，就无需区分左右孩子。而在二叉树中，即便只有一个孩子，也有左右之分。
 *
 *
 */
#ifndef BINARYTREE_H
#define BINARYTREE_H

#include <stddef.h>
#include <vector>
using namespace std;

#ifndef SAFE_DELETE
#define SAFE_DELETE(p) {if(p){free(p);p=NULL;}}
#endif

typedef struct BinaryTreeNode{
    int intData;
    char data;
    struct BinaryTreeNode *left,*right;
}BTreeNode,BTNode,*PBTree;

/************************************************
 ***************** 二叉树其他问题****************
 ************************************************/
/*1 记数
*链接：https://www.nowcoder.com/questionTerminal/f74c7506538b44399f2849eba2f050b5
*                                                  1
*                                   2                         3
*                          4             5           6             7
*                     8       9   10   11 12  13   14    15
*  如上所示，由正整数1，2，3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。
*现在的问题是，结点m所在的子树中一共包括多少个结点。     比如，n = 12，m = 3那么上图中的结点13，14，15
*以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树中共有4个结点。*/
//思路1：使用队列
void QuestionNodeCount();
//思路2：递归函数
void QuestionNodeCount2();
int QuestionNodeCount2Sub(const int m,const int n);
/*2 根据前序和中序遍历结果重构二叉树
 * 思路：前序遍历的第一项是二叉树的根结点，
 * 在中序遍历中，根结点的左侧都是根结点的左子树，右侧都是根结点的右子树。
 * 根据这个思路，使用递归函数可以重构二叉树。
 */
void Q2_ReCreate_Test();
//前序遍历并返回数据
vector<int> Q2_PreOrder(BTNode*root);
//中序遍历并返回数据
vector<int> Q2_InOrder(BTNode*root);
//重建函数（创建成功，但是打印不出来）
BTNode * Q2_ReCreate(vector<int> preVtr, vector<int> inVtr);
/* 3 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）*/
//测试函数有问题，没有解决。
void Q3_HasSubtreeTest();
bool Q3_HasSubtree(BTNode*root1,BTNode*root2);
bool Q3_IsSubtree(BTNode*root1,BTNode*root2);
/* 4 二叉树镜像
二叉树的镜像定义：
源二叉树 ：
            8
           /  \
          6   10
         / \  / \
        5  7 9 11
镜像二叉树：
            8
           /  \
          10   6
         / \  / \
        11 9 7  5
*/
void Q4_MirrorTest();
void Q4_Mirror(BTNode*root);
/*5 二叉树中和为某一值的路径
 *输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
 * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 */
void Q5_FindPathTest();
//递归方式
vector<vector<int> > Q5_FindPath_recursion(BTNode* root,int expectNumber) ;
void  Q5_FindPath_recursion_sub(BTNode* root,int expectNumber,vector<int>*intVtr,vector<vector<int> > *reIntVtr) ;




/************************************************
 ***************** 二叉树基本函数****************
 ************************************************/
//二叉树测试函数
void BinaryTreeNodeTest();

//创建树,结点个数为num
void CreateBTree(PBTree*T,int num);
void CreateBTreeSub(PBTree *T,char *array,int num);

void CreateBTree_Int(BTNode**T,const int num=10);
void CreateBTreeRecursion_Int(BTNode**T,const vector<int>&intVtr);
//销毁
void Destroy(BTNode**T);
void DestroyBTree(PBTree*T,int *count);

//遍历
//前序遍历
void PreOrderTraverse(PBTree T);
//中序遍历
void InOrderTraverse(PBTree T);
//后序遍历
void PostOrderTraverse(PBTree T);
//层遍历
void LevelOrferTraverse(PBTree T);

//深度，高度
size_t Depth(PBTree root);
//叶子结点个数
size_t LeafCount(PBTree root);
//所有结点个数
size_t NodeCount(PBTree root);
//统计度为1的结点的个数
size_t NodeOneCount(PBTree root);

//打印
void PrintBTree(PBTree T,const bool charFlag=false);//ture==char,false==int
//横向打印
void PrintBTree2(PBTree t,const int h,const bool charFlag);//ture==char,false==int
//纵向打印二叉树
void NatureDisplayTree(BTreeNode *root);

#endif // BINARYTREE_H
